#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int checkInsertionSort(int a[],int b[],int n);
int checkMergeSort(int b[],int n);
void InsertSort(int a[],int next);
void MergeSort(int a[],int n,int next_block);
void prtArr(int a[],int n);

int main(void){
	int n;
	scanf("%d",&n);
	int a[n],b[n];
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
		scanf("%d",&b[i]);
	int ret=checkInsertionSort(a,b,n);
	if( ret != -1 ){
		printf("Insertion Sort\n");
		InsertSort(b,ret);
		prtArr(b,n);
	}
	else{
		printf("Merge Sort\n");
		ret=checkMergeSort(b,n);
		MergeSort(b,n,2*ret);
		prtArr(b,n);
	}
	return 0;
}

int checkInsertionSort(int a[],int b[],int n){
	int i,ret;
	for(i=1;i<n;i++){
		if( b[i-1] <= b[i] )
			continue;
		else
			break;
	}
	ret=i;
	for(;i<n;i++){
		if( a[i] == b[i] )
			continue;
		else
			break;
	}
	if( i == n )return ret;
	else return -1;
}
void InsertSort(int a[],int n){
	int get=a[n];
	int i;
	for(i=n-1;i>=0;i--){
		if( a[i] > get ){
			a[i+1]=a[i];
		}else{
			break;
		}
	}
	a[i+1]=get;
	return ;
}
void prtArr(int a[],int n){
	int i;
	for(i=0;i<n-1;i++)
		printf("%d ",a[i]);
	printf("%d",a[i]);
	return;
}
int checkMergeSort(int b[],int n){
	int block=1;
	while( block <= n ){
		for(int i=0;i<n;i+=block){
			for(int j=1;j<block;j++){
				if( b[i+j] >= b[i+j-1] )
					continue;
				else
					return block/2;
			}
		}
		block+=block;
	}
	return block/2;
}
void ms(int a[],int b[],int n,int i1,int count1,int i2,int count2){
	int pc=i1,pa=i1,pb=i2;
	int c1=count1,c2=count2;
	while( count1 >0 && count2 >0 ){
		if( a[pa] <= a[pb] ){
			b[pc++]=a[pa++];
			count1--;
		}
		else{
			b[pc++]=a[pb++];
			count2--;
		}
	}
	while( count1-- )
		b[pc++]=a[pa++];
	while( count2-- )
		b[pc++]=a[pb++];
	memcpy(a+i1,b+i1,sizeof(int)*(c1+c2));
	return;
}
void MergeSort(int a[],int n,int block){
	int *b=malloc(sizeof(int)*n);
	int i;
	for(i=0;i+block<n;i+=block){
		ms(a,b,n,i,block/2,i+block/2,block/2);
	}
	if( n-i > block/2 )
		ms(a,b,n,i,block/2,i+block/2,n-i-block/2);
	free(b);
	return;
}
